% Define document
\documentclass[11pt]{scrartcl}

% Import packages
\usepackage[dutch,english]{babel}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{listings}
\usepackage{parskip} % split paragraphs by vertical space
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{gensymb}
\usepackage{tabularx} % for multicolumns
\usepackage{polynom} % long devision
\usepackage{pdfpages} % import pdf pages
\usepackage{verbatim} % comments
% use tikz/pgf
\usepackage{pgf}
\usepackage{tikz}
\usetikzlibrary{snakes,arrows,shapes}
\usetikzlibrary{automata}
\usepackage{graphicx}


\usepackage{tikz} 
\usetikzlibrary{calc,intersections,through,backgrounds}


% Begin document
\begin{document}
\selectlanguage{dutch}


%Add title
\title{TAI: \\
Uitwerking examenvragen}
\date{}
\maketitle



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% About
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{About}
Uitwerking van enkele examenvragen van Toepassingen van Algebra in Informatica gedoceerd in de 3e Bachelor Informatica aan de KULeuven in 2012.

Latex code van dit document te vinden op:\\
SVN checkout: \texttt{https://oefenzittingen-tai.googlecode.com/svn/trunk/}\\
Google code: \texttt{https://code.google.com/p/oefenzittingen-tai/}

Credits: Peter Roelants, Ruben Lapauw
%TODO: put your name here

Te gebruiken op eigen risico!




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% vraag
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Examen juni 2011, vraag 1}
bewijs dat $1 + 4x + 4x^2$ inverteerbaar is in $\mathbb{Z}_{16}[x]$



\subsection{Oplossing (door Ruben Lapauw)}
Opmerking: $\mathbb{Z}_{16}$ is geen veld, het is een ring. Ringen hebben nuldelers, bijvoorbeeld $4*4 = 0$. Er is geen irreduceerbare veelterm die dit veld opgesteld heeft, als je er toch 1 moet zoeken zou deze 16 zijn, want je hebt de restklassen van $\mathbb{Z}$ uitgedeeld door 16.

$1 = (1+4x+4x^2) (a_0 + a_1 x + a_2 x^2 + \ldots)$\\
$\Leftrightarrow$\\
$1 = a_0 + (a_1 + 4 a_0)x + ( a_2 + 4 a_1 + 4 a0) x^2 + \ldots + (a_k + 4 a_{k-1} + 4 a_{k-2})  x^k + \ldots $\\
$\Leftrightarrow$\\
$1 = a_0$\\
$0 = a_1 + 4*1 \Rightarrow a_1 = 12$  ($<\mathbb{Z}_{16},+>$ is een groep, heeft inverse) \\
$0 = a_2 + 4*12 + 4 \Rightarrow a_2 = 12$ \\
$0 = a_3 + 4*12 + 4*12 \Rightarrow a_3 = 0$\\
$0 = a_4 + 4*0 + 4*12 \Rightarrow a_4 = 0$\\
$0 = a_5 + 4*0 + 4*0 \Rightarrow a_5 = 0$\\
$\ldots$\\
$\Rightarrow a_k = 0 (k>2)$ (inductie)


Dus het inverse is $1 + 12x + 12x^2$

Dis is misschien wel wat overkill, practisch kan je beginnen met 0-de graad, en iedere keer een graad hoger gaan als het niet lukt.




\subsection{oplossing (meer practisch)}
Inverteerbaar wil zeggen dat er voor $x = 1 + 4x + 4x^2$ een inverse $x^{-1}$ bestaat zodat $x * x^{-1} = 1$. We zoeken dus een veelterm $x^{-1}$ die als product met $x$ het eenheidselement 1 geeft.

We gaan dit iteratief bepalen:
Stel $x^{-1}$ een veelterm van de 0-de graad: $x^{-1} = a_0$\\
$\Rightarrow 1 = (1 + 4x + 4x^2) * a_0$\\
$\Rightarrow 1 = a_0 + 4a_0 x + 4a_0 x^2$\\
$\Rightarrow
\begin{cases} 
1 = a_0 \\
0 = 4 * a_0 \\
0 = 4 * x_0 \\ 
\end{cases} 
$\\
Dit stelsel heeft geen oplossing, en dus is de inverse van $x$ al geen 0-de graads veelterm.

\vspace{0.5cm}
Stel $x^{-1}$ een veelterm van de 1-de graad: $x^{-1} = a_0 + a_1 x $\\
$\Rightarrow 1 = (1 + 4x + 4x^2) * (a_0 + a_1 x)$\\
$\Rightarrow 1 = a_0 + (a_1 + 4a_0)x + (4a_1 + 4a_0)x^2 + 4a_1x^3$\\
$\Rightarrow
\begin{cases} 
1 = a_0 \\
0 = a_1 + 4a_0 \\
0 = 4a_1 + 4a_0 \\
0 = 4a_1 \\ 
\end{cases} 
$\\
Dit stelsel heeft geen oplossing, en dus is de inverse van $x$ ook al geen 1-e graads veelterm.


\vspace{0.5cm}
Stel $x^{-1}$ een veelterm van de 2-de graad: $x^{-1} = a_0 + a_1 x + a_2 x^2 $\\
$\Rightarrow 1 = (1 + 4x + 4x^2) * (a_0 + a_1 x + a_2 x^2)$\\
$\Rightarrow 1 = a_0 + (a_1 + 4a_0)x + (a_2 + 4a_1 + 4a_0)x^2 + (4a_2 + 4a_1)x^3 + (4a_2)x^4$\\
$\Rightarrow
\begin{cases} 
1 = a_0 \\
0 = a_1 + 4a_0 \\
0 = a_2 + 4a_1 + 4a_0 \\
0 = 4a_2 + 4a_1 \\ 
0 = 4a_2 \\ 
\end{cases} 
$\\
Dit stelsel heeft de volgende oplossing:\\
$
\begin{cases} 
a_0 = 1\\
a_1 = 12\\
a_2 = 12\\
\end{cases} 
$

$\Rightarrow x^{-1} = 1 + 12 x + 12 x^2$, met $x^{-1}$ de inverse van $x = 1 + 4x + 4x^2$.






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% vraag
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Examen juni 2011, vraag 2}
(8,6) Hamming code GF(7)

$H =
\begin{bmatrix}
	1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
	0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 
\end{bmatrix}$

(a) $G$?

(b) codeer $i=400306$

(c) decodeer $v=60342545$ wat is $i$?

(Hamming code: p.47 cursus)



\subsection{oplossing (a)}

\[
H =
\begin{bmatrix}
	1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
	0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 
\end{bmatrix}
=
[-P^T | I]
\]
\[
\Rightarrow H' = 
\begin{bmatrix}
	5 & 6 & 1 & 2 & 3 & 4 & 1 & 0 \\
	1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 
\end{bmatrix}
\]
\begin{center}
(kolompermutatie: 12345678 $\rightarrow 78234512$)
\end{center} 
\[
\Rightarrow -P^T = 
\begin{bmatrix}
	5 & 6 & 1 & 2 & 3 & 4 \\
	1 & 1 & 1 & 1 & 1 & 1 
\end{bmatrix}
\Rightarrow
P = 
\begin{bmatrix}
	-5 & -1 \\
	-6 & -1 \\
	-1 & -1 \\
	-2 & -1 \\
	-3 & -1 \\
	-4 & -1
\end{bmatrix}
=
\begin{bmatrix}
	2 & 6 \\
	1 & 6 \\
	6 & 6 \\
	5 & 6 \\
	4 & 6 \\
	3 & 6
\end{bmatrix}
\]

\[
G' = [I | P] =
\begin{bmatrix}
	1 & 0 & 0 & 0 & 0 & 0 & 2 & 6 \\
	0 & 1 & 0 & 0 & 0 & 0 & 1 & 6 \\
	0 & 0 & 1 & 0 & 0 & 0 & 6 & 6 \\
	0 & 0 & 0 & 1 & 0 & 0 & 5 & 6 \\
	0 & 0 & 0 & 0 & 1 & 0 & 4 & 6 \\
	0 & 0 & 0 & 0 & 0 & 1 & 3 & 6
\end{bmatrix}
\]
\[
\Rightarrow G =
\begin{bmatrix}
	2 & 6 & 0 & 0 & 0 & 0 & 1 & 0 \\
	1 & 6 & 0 & 0 & 0 & 0 & 0 & 1 \\
	6 & 6 & 1 & 0 & 0 & 0 & 0 & 0 \\
	5 & 6 & 0 & 1 & 0 & 0 & 0 & 0 \\
	4 & 6 & 0 & 0 & 1 & 0 & 0 & 0 \\
	3 & 6 & 0 & 0 & 0 & 1 & 0 & 0
\end{bmatrix}
\]
\begin{center}
(kolompermutatie: 12345678 $\rightarrow 78234512$)
\end{center}





\subsection{oplossing (b)}
\[
c = i G =
\begin{bmatrix}
	4 & 0 & 0 & 3 & 0 & 6
\end{bmatrix}
*
\begin{bmatrix}
	2 & 6 & 0 & 0 & 0 & 0 & 1 & 0 \\
	1 & 6 & 0 & 0 & 0 & 0 & 0 & 1 \\
	6 & 6 & 1 & 0 & 0 & 0 & 0 & 0 \\
	5 & 6 & 0 & 1 & 0 & 0 & 0 & 0 \\
	4 & 6 & 0 & 0 & 1 & 0 & 0 & 0 \\
	3 & 6 & 0 & 0 & 0 & 1 & 0 & 0
\end{bmatrix}
\]
\[
=
\begin{bmatrix}
	6 & 1 & 0 & 3 & 0 & 6 & 4 & 0
\end{bmatrix}
\]



\subsection{oplossing (c)}
\[
s = v H^T = 
\begin{bmatrix}
	6 & 0 & 3 & 4 & 2 & 5 & 4 & 5
\end{bmatrix}
*
\begin{bmatrix}
	1 & 0 \\
	0 & 1 \\
	1 & 1 \\
	2 & 1 \\
	3 & 1 \\
	4 & 1 \\
	5 & 1 \\
	6 & 1
\end{bmatrix}
\]
\[
=
\begin{bmatrix}
	2 & 2
\end{bmatrix}
\]
\begin{center}
= 2 keer kolom 3 van $H$ =
$
\begin{bmatrix}
	0 & 0 & 2 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}
*
H^T
$
\end{center}
\[
\Rightarrow e =
\begin{bmatrix}
	0 & 0 & 2 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}
\]
\[
\Rightarrow c =
v - e
=
\begin{bmatrix}
	6 & 0 & 1 & 4 & 2 & 5 & 4 & 5
\end{bmatrix}
\]

Om vervolgens $i$ te vinden doen we dezelfde kolompermutaties van $G \rightarrow G'$ op $c$ zodat we $c'$ bekomen. (kolompermutatie: $12345678 \rightarrow 78234512$).

\[\Rightarrow c' =
\begin{bmatrix}
	4 & 5 & 1 & 4 & 2 & 5 & 6 & 0
\end{bmatrix}
\]

En vervolgens nemen we de eerste $d$ elementen van $c'$ om $i$ te bekomen, met $d$ het aantal rijen van $G$.\\
\[\Rightarrow i =
\begin{bmatrix}
	4 & 5 & 1 & 4 & 2 & 5
\end{bmatrix}
\]








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% vraag
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Examen 25 augustus 2008, vraag 1}
Gegeven volgende simpele code: Een infowoord van 3 tekens (modulo 3), $abc$ wordt omgezet in een codewoord als volgt: $abcde$, met $abc$ gelijk aan $abc$ uit het informatiewoord, en de zodat $d+a+c=0$ en zodat $a+e=0$. Wat is de lengte van de code, hoeveel fouten kan ze verbeteren en hoeveel fouten kan ze vinden? Dimensie van de code? Is het een lineaire code? Is het een cyclische code? Stel een generatormatrix op voor deze code.



\subsection{oplossing}

Informatiewoord: $abc$ $\Rightarrow$ lengte = 3 = $k$.\\
Codewoord: $abcde$ $\Rightarrow$ lengte = 5 = $n$.\\
$\Rightarrow$ We hebben te maken met een 3-dimensionale deelruimte $\mathbb{C}$ van $\mathbb{R} = GF(3)^5$, een lineaire blokcode: $(5,3)-code$. (p.39 cursus)

We gaan eerst de generatormatrix $G$ proberen te zoeken.

$c$ kunnen we uitdrukken als $c = i G$.\\
Aangezien $c = [abcde]$ en $i = [abc]$ is $G$ een (3x5) matrix.\\
\[
c = i G \Rightarrow
\begin{bmatrix}
	a & b & c & d & e
\end{bmatrix}
=
\begin{bmatrix}
	a & b & c
\end{bmatrix}
*
\begin{bmatrix}
	G_{00}	&	G_{01}	&	G_{02}	&	G_{03}	&	G_{04} \\
	G_{10}	&	G_{11}	&	G_{12}	&	G_{13}	&	G_{14} \\
	G_{20}	&	G_{21}	&	G_{22}	&	G_{23}	&	G_{24}
\end{bmatrix}
\]
De eerste drie kolommen van $G$ kunnen we makkelijk invullen aangezien $[abc] * G = [abc|de]$.
\[
\begin{bmatrix}
	a & b & c
\end{bmatrix}
*
\begin{bmatrix}
	1	&	0	&	0	&	G_{03}	&	G_{04} \\
	0	&	1	&	0	&	G_{13}	&	G_{14} \\
	0	&	0	&	1	&	G_{23}	&	G_{24}
\end{bmatrix}
=
\begin{bmatrix}
	a & b & c & d & e
\end{bmatrix}
\]
De laatste twee kolommen kunnen we vinden doordat we weten dat $d+a+c=0$ en $a+e=0$.
\[
d+a+c=0 \Rightarrow d = -a -c \pmod3 = 2a + 2c
\]
\[
a+e=0 \Rightarrow e = -a \pmod3 = 2a
\]
\[
\Rightarrow
\begin{bmatrix}
	a & b & c
\end{bmatrix}
*
\begin{bmatrix}
	1	&	0	&	0	&	2	&	2 \\
	0	&	1	&	0	&	0	&	0 \\
	0	&	0	&	1	&	2	&	0
\end{bmatrix}
=
\begin{bmatrix}
	a & b & c & d & e
\end{bmatrix}
\]
Dus:
\[
G = 
\begin{bmatrix}
	1	&	0	&	0	&	2	&	2 \\
	0	&	1	&	0	&	0	&	0 \\
	0	&	0	&	1	&	2	&	0
\end{bmatrix}
\]
De code is dus een lineaire code met dimensie $k = 3$ en lengte $n = 5$.

Vervolgens willen we weten hoeveel fouten deze code kan verbeteren. Dit kunnen we doe door alle codewoorden te bepalen en het minimale gewicht te bepalen:

\begin{comment}
%Matlab code om volgende rap te genereren:
G = [ 1 0 0 2 2; 0 1 0 0 0; 0 0 1 2 0]
i = [ 0 0 0 ]
for a = 0:2
    i(1) = a;
    for b = 0:2
        i(2) = b;
        for c = 0:2
            i(3) = c;
            i_str = num2str(i);
            G_str = num2str(mod(i*G, 3));
            s = ['$','[',i_str,']',' \rightarrow ','[',G_str,']','$'];
            disp(s)
            
        end
    end
end
\end{comment}

\begin{tabularx}{\textwidth}{XXX}
$[0  0  0] \rightarrow [0  0  0  0  0]$

$[0  0  1] \rightarrow [0  0  1  2  0]$

$[0  0  2] \rightarrow [0  0  2  1  0]$

$[0  1  0] \rightarrow [0  1  0  0  0]$

$[0  1  1] \rightarrow [0  1  1  2  0]$

$[0  1  2] \rightarrow [0  1  2  1  0]$

$[0  2  0] \rightarrow [0  2  0  0  0]$

$[0  2  1] \rightarrow [0  2  1  2  0]$

$[0  2  2] \rightarrow [0  2  2  1  0]$

&

$[1  0  0] \rightarrow [1  0  0  2  2]$

$[1  0  1] \rightarrow [1  0  1  1  2]$

$[1  0  2] \rightarrow [1  0  2  0  2]$

$[1  1  0] \rightarrow [1  1  0  2  2]$

$[1  1  1] \rightarrow [1  1  1  1  2]$

$[1  1  2] \rightarrow [1  1  2  0  2]$

$[1  2  0] \rightarrow [1  2  0  2  2]$

$[1  2  1] \rightarrow [1  2  1  1  2]$

$[1  2  2] \rightarrow [1  2  2  0  2]$

&

$[2  0  0] \rightarrow [2  0  0  1  1]$

$[2  0  1] \rightarrow [2  0  1  0  1]$

$[2  0  2] \rightarrow [2  0  2  2  1]$

$[2  1  0] \rightarrow [2  1  0  1  1]$

$[2  1  1] \rightarrow [2  1  1  0  1]$

$[2  1  2] \rightarrow [2  1  2  2  1]$

$[2  2  0] \rightarrow [2  2  0  1  1]$

$[2  2  1] \rightarrow [2  2  1  0  1]$

$[2  2  2] \rightarrow [2  2  2  2  1]$
\end{tabularx}

We zien dus dat het minimale gewicht $d = 1$. Deze code kan dus geen enkele fout detecteren of verbeteren.

Deze code is geen cyclische code, want we zien al dat $[0  0  1  2  0]$ geen cyclische right shift heeft ($[0 0  0  1  2]$). (zie p. 50 cursus)






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% vraag
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Examen 25 augustus 2008, vraag 2}
BCH-code in $GF(8)$, $n=15$ en moet 2 fouten kunnen verbeteren ($t=2$). Bepaal hoeveel verschillende codes je hiervoor kan construeren, en wat is de optimale code, en hoeveel mogelijke optimale codes zijn er?

Tip: je mag $l$ vrij kiezen, varieer deze van 0 tot 14, bepaal de cyclotomische nevenklassen en hun minimaalveeltermen. 
Je moet werken met een $GF(8^4)$ code over $GF(8)$ (want $8^4 \pmod{15}=1$). Dit wil ook zeggen dat er maximaal 5 elementen in een cyclotomische nevenklasse zitten. 
Schrijf dan voor elke waarde van $l$ de combinatie van minimaalveeltermen uit die de generatorveelterm $g(x)$ vormen ($2t$ opeenvolgende machten van $\beta$). Schrap dan alle identieke $g(x)$. Wat je overhoudt is het aantal (en welke) mogelijke generatorveeltermen en dus verschillende codes. Voor het bepalen van de effici\"entie van de code, zeg je dat de code een $(n,k)$-code is, met $k=n-(\text{graad}(g(x))$

BCH-code: p.58 cursus.




\subsection{oplossing}
Om te bepalen hoeveel verschillende codes we hiervoor kunnen construeren, en hoeveel optimale codes er zijn moeten we de cyclotomische nevenklassen van $\beta$ (primitief element van $GF(8^4)$) bepalen.

Het berekenen van het volgende element van de nevenklasse gebeurt door het vorige element met $q \pmod{n} = 8 \pmod{15}$ te vermenigvuldigen.

$C_0 = \{ 0 \}$\\
$C_1 = \{ 1, 8, 4, 2 \}$\\
$C_3 = \{ 3, 9, 12, 6 \}$\\
$C_5 = \{ 5, 10 \}$\\
$C_7 = \{ 7, 11, 13, 14 \}$

Om $t=2$ fouten te kunnen verbeteren moeten we een generatorveelterm $g(x)$ vormen uit een combinatie van minimaalveeltermen, die uit $2t = 4$ opeenvolgende machten van $\beta$ bestaat.
De volgende combinaties zijn dus mogelijke opties:

Verbeterd 2 fouten:\\
$l = 1 \rightarrow \{ \beta^1, \beta^2, \beta^3, \beta^4\} = C_1, C_3$\\
$l = 0 \rightarrow \{ \beta^0, \beta^1, \beta^2, \beta^3, \beta^4\} = C_0, C_1, C_3$\\
$l = 11 \rightarrow \{ \beta^{11}, \beta^{12}, \beta^{13}, \beta^{14}\} = C_3, C_7$

Verbeterd 3 fouten:\\
$l = 1 \rightarrow \{\beta^1, \beta^2, \beta^3, \beta^4, \beta^5, \beta^6\} = C_1, C_3, C_5$\\
$l = 0 \rightarrow \{\beta^0, \beta^1, \beta^2, \beta^3, \beta^4, \beta^5, \beta^6\} = C_0, C_1, C_3, C_5$\\
$l = 9 \rightarrow \{\beta^9, \beta^{10}, \beta^{11}, \beta^{12}, \beta^{13}, \beta^{14}\} = C_3, C_5, C_7$

Verbeterd 7 fouten:\\
$l = 1 \rightarrow \{ \beta^1, \beta^2, \beta^3, \beta^4, \beta^5, \beta^6, \beta^7, \beta^8, \beta^9, \beta^{10}, \beta^{11}, \beta^{12}, \beta^{13}, \beta^{14}\} = C_1, C_3, C_5, C_7$\\
$l = 0 \rightarrow \{ \beta^0, \beta^1, \beta^2, \beta^3, \beta^4, \beta^5, \beta^6, \beta^7, \beta^8, \beta^9, \beta^{10}, \beta^{11}, \beta^{12}, \beta^{13}, \beta^{14}\} = C_0, C_1, C_3, C_5, C_7$

Er zijn dus in totaal 8 verschillende codes die en tenminste $t=2$ fouten kunnen verbeteren, waarvan 3 exact $t=2$ fouten kunnen verbeteren.

Er zijn 2 optimale codes: $l=1$ $(C_1, C_3)$, en $l=11$ $(C_3, C_7)$. Deze hebben beiden een graad van 8 en zijn dus $(14,6)$ codes.







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% vraag
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Examen 25 augustus 2008, vraag 3}
BCH code over $GF(19)$, $n=18$ (dus je hebt een $GF(19)$ over $GF(19)$ code ($k=1$)) en $t=2$ Bepaal $g(x)$, je mag zelf $l$ kiezen. (omdat $k=1$ heeft elke cyclotomische nevenklasse juist 1 element en is de graad van $g(x)$ altijd even groot, ongeacht de keuze van je $l$) Bepaal de dimensie van de code. Codeer een zelfgekozen infowoord met $d \geq 2$ (doe dit ook zo simpel mogelijk, kies dus 2 tekens verschillend van 0, dat spaart veel rekenwerk uit). Zet in het bekomen codewoord 2 zelfgekozen fouten, decodeer dit woord terug met BM en Forney. (Voor het bepalen van de syndromen mag je gebruik maken van het feit dat je de foutlocaties al kent).


\subsection{oplossing}
$GF(19)$ kan niet opgesplits worden naar een kleiner veld, want 19 is een priemgetal.

Elk element buiten 1 uit de multiplicatieve groep van $GF(19) = \mathbb{Z}_{19}$ is een primitief element van deze multiplicatieve groep (zie p.20 cursus). We kunnen dus bijvoorbeeld het element $\alpha = 2$ nemen als ons primitief element (dit hoort bij de primitieve veelterm $(x - 17)$). De rest van de elementen kan dus als volgt bepaald worden:

\begin{tabularx}{\textwidth}{XXX}

$\alpha^0 = 1$

$\alpha^1 = 2$

$\alpha^2 = 4$

$\alpha^3 = 8$

$\alpha^4 = 16$

$\alpha^5 = 13$

$\alpha^6 = 7$

&

$\alpha^7 = 14$

$\alpha^8 = 9$

$\alpha^9 = 18$

$\alpha^{10} = 17$

$\alpha^{11} = 15$

$\alpha^{12} = 11$

&

$\alpha^{13} = 3$

$\alpha^{14} = 6$

$\alpha^{15} = 12$

$\alpha^{16} = 5$

$\alpha^{17} = 10$

$\alpha^{18} = 1$

\end{tabularx}


Omdat $k=1$ heeft elke cyclotomische nevenklasse juist 1 element. Elke cyclotomische nevenklassen komt dus overeen met het enige element dat er in zit.

Om de generatorveelterm te berekenen nemen we bijvoorbeeld $l=0$:
\[
g(x) = (x - \alpha^0)(x - \alpha^1)(x - \alpha^2)(x - \alpha^3)
\]
\[
= (x + 18)(x + 17)(x + 15)(x + 11)
\]
\[
= 7 + 13 x + 13 x^2 + 4 x^3 + x^4
\]

De dimensie van deze code is $n - graad(g(x)) = 18 - 4 = 14$. $g(x)$ bepaald dus een $(18,14)$ code over $GF(19)$.


We kunnen vervolgens een willekeurig infowoord kiesen, \\
vb $i = $[2 1 0 0 0 0 0 0 0 0 0 0 0 0]$ = (2 + x)$

dan is $c(x) = i(x)*g(x) = 14 + 14 x + x^2 + 2 x^3 + 6 x^4 + x^5$\\
= [14 14 1 2 6 1 0 0 0 0 0 0 0 0 0 0 0 0]


enzoverder\ldots








\end{document}
